`
https://leetcode.cn/problems/word-break/
`

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  // 存储已经计算过的后缀字串
  const memo = new Set()
  let isFound = false

  function backtrack(i) {
    if (isFound) return

    if (i === s.length) {
      isFound = true
      return
    }

    // 新增的剪枝逻辑，查询子串（子树）是否已经计算过
    const suffix = s.substring(i);
    if (memo.has(suffix)) {
      // 当前子串（子树）不能被切分，就不用继续递归了
      return;
    }

    for (const word of wordDict) {
      const len = word.length
      if (s.length - i < len || s.substring(i, i + len) !== word) continue
      backtrack(i + len)
    }

    // 后序位置，将不能切分的子串（子树）记录到备忘录
    if (!isFound) {
      memo.add(suffix);
    }
  }
  backtrack(0)

  return isFound
};